|
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems. The Turing degree of a set tells how difficult it is to solve the decision problem associated with the set, that is, to determine whether an arbitrary number is in the given set. Two sets are Turing equivalent if they have the same level of unsolvability; each Turing degree is a collection of Turing equivalent sets, so that two sets are in different Turing degrees exactly when they are not Turing equivalent. Furthermore, the Turing degrees are partially ordered so that if the Turing degree of a set ''X'' is less than the Turing degree of a set ''Y'' then any (noncomputable) procedure that correctly decides whether numbers are in ''Y'' can be effectively converted to a procedure that correctly decides whether numbers are in ''X''. It is in this sense that the Turing degree of a set corresponds to its level of algorithmic unsolvability. The Turing degrees were introduced by Emil Leon Post (1944), and many fundamental results were established by Stephen Cole Kleene and Post (1954). The Turing degrees have been an area of intense research since then. Many proofs in the area make use of a proof technique known as the priority method. == Turing equivalence == (詳細はTuring reducible to a set ''Y'' if there is an oracle Turing machine that decides membership in ''X'' when given an oracle for membership in ''Y''. The notation ''X'' ≤T ''Y'' indicates that ''X'' is Turing reducible to ''Y''. Two sets ''X'' and ''Y'' are defined to be Turing equivalent if ''X'' is Turing reducible to ''Y'' and ''Y'' is Turing reducible to ''X''. The notation ''X'' ≡T ''Y'' indicates that ''X'' and ''Y'' are Turing equivalent. The relation ≡T can be seen to be an equivalence relation, which means that for all sets ''X'', ''Y'', and ''Z'': * ''X'' ≡T ''X'' * ''X'' ≡T ''Y'' implies ''Y'' ≡T ''X'' * If ''X'' ≡T ''Y'' and ''Y'' ≡T ''Z'' then ''X'' ≡T ''Z''. A Turing degree is an equivalence class of the relation ≡T. The notation () denotes the equivalence class containing a set ''X''. The entire collection of Turing degrees is denoted . The Turing degrees have a partial order ≤ defined so that () ≤ () if and only if ''X'' ≤T ''Y''. There is a unique Turing degree containing all the computable sets, and this degree is less than every other degree. It is denoted 0 (zero) because it is the least element of the poset . (It is common to use boldface notation for Turing degrees, in order to distinguish them from sets. When no confusion can occur, such as with (), the boldface is not necessary.) For any sets ''X'' and ''Y'', X join Y, written ''X ⊕ Y'', is defined to be the union of the sets } and }. The Turing degree of ''X ⊕ Y'' is the least upper bound of the degrees of ''X'' and ''Y''. Thus is a join-semilattice. The least upper bound of degrees a and b is denoted a ∪ b. It is known that is not a lattice, as there are pairs of degrees with no greatest lower bound. For any set ''X'' the notation ''X''′ denotes the set of indices of oracle machines that halt when using ''X'' as an oracle. The set ''X''′ is called the Turing jump of ''X''. The Turing jump of a degree () is defined to be the degree (); this is a valid definition because ''X''′ ≡T ''Y''′ whenever ''X'' ≡T ''Y''. A key example is 0′, the degree of the halting problem. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turing degree」の詳細全文を読む スポンサード リンク
|